COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\MOBDR25\M1BDI25\M2NGB25\M3XMAS25\. 
C00011 00003	
C00013 ENDMK
C⊗;
\\MOBDR25;\M1BDI25;\M2NGB25;\M3XMAS25;\. 
\F0\CELEMENTARY AND RECURSIVE PROGRAMS AND SCHEMES


\J	This is a field in which there is no agreed upon terminology in
spite of the fact that the entities involved have been studied for a
number of years.  The terminology used here does not correspond to
that used by anyone elsewhere.

	The easiest way to look at the matter is to say that we start
with a collection \F3F\F0 of functions and predicates and we want to
build up the collection of programs or functions that can be built up
from them.  What  programs and functions we end up with will depend on
what processes we allow for building.  Moreover, in order to get a definite
concept we need to be precise about the domains and ranges  of the
initial functions and the built-up functions.

	However, it is often desirable to be more abstract.  Instead of
starting with functions, we start with just symbols for functions.  We
build "programs" or "functions" from these symbols and only later consider
what functions these symbols are to represent.  Thus we are interested
in what \F1program\F0 we get from a \F1program scheme\F0 under various
\F1interpretations\F0 of the \F1function symbols\F0.

	Now we can make the formal definitions, but we are not interested
in syntax at present so we shall not be precise about syntactic entities.

\F2Definition 1 -\F0 A \F1term\F0 is a variable or a string of symbols
built up from variables and function symbols by applying the function
symbols to subexpressions in the usual way.  In a term per se,
the function symbols have no interpretation yet.  We shall also allow
infixes like + to be used and regard them also as uninterpreted function
symbols.  Each function symbol will be used with a fixed number of arguments
and we shall consider that the number of arguments is a property of the
symbol.  Infixes like + that normally represent associative functions
may be used with variable numbers of arguments, but then we shall assign
to them only associative functions as interpretations.

\F2Definition\F0 2 - A \F1conditional expression\F0 is an expression of the
form

	\F2if\F1 p \F2then\F1 a \F2else\F1 b\F0.

where \F1p, a, \F0and \F1b\F0 are terms.

\F2Definition\F0 3 - An \F1extended term\F0 is a string of symbols formed
by the same rule as terms except that conditional expressions are allowed
to be used anywhere a term is allowed.

\F2Definition\F0 4 - An \F1interpretation\F0 of a collection \F3F\F0 of
function symbols and variables is an assignment to each
function symbol of a function taking
arguments in certain domains and taking its value in a certain domain.
Each variable is assigned a domain, but not a value.
Predicates are functions which take values in the domain {\F2true,false\F0},
and constants are functions of zero arguments and are allowed.

\F2Definition\F0 5 - An interpretation \F1I interprets\F0 a term or extended
term \F1e\F0 if

	(i) every function or variable occurring in \F1e\F0 is assigned
a function or domain respectively by \F1I\F0, and

	(ii) there is an assignment of domains to \F1e\F0
and every subterm of e such that
the variables get the same domains as given by \F1I\F0, every term occurring
as an argument of a function symbol is assigned the domain assigned by \F1I\F0
to that place of the function symbol, a term formed by applying a function
symbol \F1f\F0 is assigned the range of \F1f\F0 as domain, the \F1p\F0-term
in a conditional expression is assigned the domain {\F2true,false\F0},
and the \F1a\F0 and \F1b\F0 terms of a conditional expression are assigned the
same domain which is also the domain assigned to the conditional expression
as a whole.

	The above assignment of domains to \F1e\F0 and its subexpressions
is easily seen to be unique, and the domain assigned to \F1e\F0 thereby is
called the domain assigned to \F1e\F0 by \F1I\F0.

\F2Definition\F0 6 - A \F1simple assignment statement\F0 has the form

	\F1v\F0 ← \F1e\F0,

where \F1v\F0 is a variable and \F1e\F0 is a form.

\F2Definition\F0 8 - A \F0labelled assignment statement\F0 has the form

	\F1l\F0: \F1a\F0,

where \F1l\F0 is a symbol serving as a label and \F1a\F0 is a simple
assignment statement.  An \F1assignment statement\F0 is either a simple
assignement statement or a labelled assignment statement.

\F2Definition\F0 9 - A \F1go-to statement\F0 has the form

	\F2if \F1p\F2 then go to \F1l\F0,

where \F1p\F0 is a term and \F1l\F0 is a label.

\F2Definition\F0 10 - A \F1simple program scheme\F0 is a sequence of assignment
and go-to statements satisfying the condition that no label labels more than
one statement and each label in a go-to statement labels some statement.

\F2Definition\F0 11 - A \F1simple program\F0 consists of a simple program scheme
and an interpretation \F1I\F0 of the collection of functions and variables occurring
in the program satisfying the following conditions:

	(i) The \F1p\F0 term in a go-to statement is assigned the
domain {\F2true,false\F0} in \F1I\F0.

	(ii) For each assignment statement, the left hand side is assigned
the same domain as the right hand side.

\F2Definition\F0 12 - Let \F1u\F0 be one of the variables of a program \F1P\F0,
and let \F1x,...,z\F0 be the variables of \F1P\F0.  Let there be \F1k\F0
variables in \F1P\F0 altogether.  Let \F1f\F0 be a partial function of \F1k\F0
whose arguments come from the domains of the variables \F1x,...,z\F0 and whose
range is the domain of the variable \F1u\F0.  We shall say that \F1f\F0 is
computed by \F1P\F0 if ...

\F2Theorem\F0 1 - Any partial function computable by a simple program
in \F3F\F0 is computable by a recursive function in \F3F\F0.

\F2Proof\F0 -

\F2Theorem\F0 2 - Any partial function computable by a recursive function
in \F3F\F0 is computable by a simple program in \F3F\F0 if \F3F\F0 contains
the functions \F1car, cdr,\F0 and \F1cons\F0.

\F2Theorem\F0 3 - (in Hewitt and Paterson \F1Comparative Schematology\F0)
The recursive function given by the scheme

	\F1f\F0(\F1x\F0) ← \F2if\F1 p\F0(\F1x\F0) \F2then 
			\F0(\F2if \F1q\F0(\F1x\F0) \F2then true else false\F0)
		\F2else if \F1f\F0(\F1l\F0(\F1x\F0)) \F2then true
		else \F1f\F0(\F1r\F0(\F1x\F0)),

is not always computable by a simple program in {\F1p,q,l,r\F0}.\.